﻿#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#define RANDOM_RANGE 1000
#include <time.h>



/* Do not modify this part */
void generateRandom(int **arr, int size)
{
    if (*arr == NULL)
        *arr = (int *)malloc(sizeof(int) * size);
    int *ptr = *arr;
    for (int i = 0; i < size; i++)
    {
        ptr[i] = rand() % RANDOM_RANGE;
    }
}

void displayArr(int *arr, int size)
{
    if (arr != NULL)
    {
        for (int i = 0; i < size; i++)
        {
            printf("%d ", arr[i]);
        }
        printf("\n");
    }
}



/*------------------------------Solution Starts------------------------*/

// implement three sorting algorithms...


void BubbleSort(int *arr, int n)
{
	int flag;
	for(int i=0;i<n-1;i++){
        flag=0;
        for(int j=0;j<n-i-1;j++){
            if(arr[j+1]<arr[j]){
                //swap when left number is bigger than right number
                int temp=arr[j+1];
                arr[j+1]=arr[j];
                arr[j]=temp;
                flag=1;
            }
        }
        if(flag==0)
            break;//no more swapping, exit
    }
}


void InsertionSort(int *arr, int n)
{
    for(int p=1;p<n;p++){
        int key=arr[p];//pick out key number
        int i=p-1;//start compare from key number's left
        while (i>=0&&arr[i]>key){
            arr[i+1]=arr[i];
            i--;
        }//when the current left number is bigger than the key number, move current number right
        arr[i+1]=key;//insert the key number to the correct position 
    }  
}


void merge(int arr[], int left, int middle, int right)
{
    int *tempArr=(int*)malloc(sizeof(int)*(right-left+1));//create a temporary array 
    int i1=left;//left part first number
    int i2=middle+1;//right part first number
    int i=0;//merged array first number
    while(i1<=middle&&i2<=right){//both left part and right part have numbers
        if(arr[i1]<arr[i2])
            tempArr[i++]=arr[i1++];
        else
            tempArr[i++]=arr[i2++];
    }
    while(i1<=middle)//put in left remain numbers
        tempArr[i++]=arr[i1++];
    while(i2<=right)//put in right remain numbers
        tempArr[i++]=arr[i2++];
    for(int j=0;j<=right-left;j++){//copy merged array into the original array
        arr[left+j]=tempArr[j];
    }
    free(tempArr);//free the memory
}

void MergeSort(int *arr, int l, int r)
{
    if(l>=r)
        return;//only one number, exit
    int mid=(l+r)/2;
    MergeSort(arr,l,mid);//left part
    MergeSort(arr,mid+1,r);//right part
    merge(arr,l,mid,r);
}




/*------------------------------Solution Ends------------------------*/



/*Do not change the main method */

int main(void)
{
    // Don't change this
    srand(1);

    /* First generate A1, A2 and A3 with size=10*/
    int size = 10;
    int *A1 = NULL;

    // A1
    generateRandom(&A1, size);
    displayArr(A1, size);
    
	// A2
    int *A2 = (int *)malloc(sizeof(int) * size);
    memcpy(A2, A1, sizeof(int) * size);
    displayArr(A2, size);

    // A3
	int *A3 = (int *)malloc(sizeof(int) * size);
    memcpy(A3, A1, sizeof(int) * size);
    displayArr(A3,size);


    printf("Value of A1 after BubbleSort:\n");
    BubbleSort(A1, size);
    displayArr(A1, size);


    printf("Value of A2 after InsertionSort:\n");
    InsertionSort(A2, size);
    displayArr(A2, size);
   
    printf("Value of A3 after MergeSort:\n");
    MergeSort(A3, 0, size - 1);
    displayArr(A3, size);

    // prevent memory leak!
    free(A1);
    free(A2);
    free(A3);
    A1 = NULL;
    A2 = NULL;
    A3 = NULL;

    
	
	// for larger array
    size = 100000;
    generateRandom(&A1, size);
    A2 = (int *)malloc(sizeof(int) * size);
    memcpy(A2, A1, sizeof(int) * size);

    A3 = (int *)malloc(sizeof(int) * size);
    memcpy(A3, A1, sizeof(int) * size);

	clock_t begin, end;

	// For BubbleSort
    begin = clock();
    BubbleSort(A1, size);
    end = clock();
    printf("BubbleSort Lasting: %f seconds\n", (double)(end - begin) /CLOCKS_PER_SEC);
    
	

    // For InsertionSort
    begin = clock();
    InsertionSort(A2, size);
    end = clock();
    printf("InsertionSort Lasting: %f seconds\n", (double)(end - begin) /CLOCKS_PER_SEC);

    // For MergeSort
    begin = clock();
    MergeSort(A3, 0, size - 1);
    end = clock();
    printf("MergeSort Lasting: %f seconds\n", (double)(end - begin) /CLOCKS_PER_SEC);


    free(A1);
    free(A2);
    free(A3);
    A1 = NULL;
    A2 = NULL;
    A3 = NULL;

	
    return 0;
}
